package com.kznnc.data_structure.sort.two;

/**
 * @Description 快速排序
 * 核心思路:
 * 基准数: 基准数的选择是很有讲究的  一基准数的选择会决定快速排序的效率
 * 基准数: 一般就是去要排序序列的第一个
 * 45 28 80 90 50 16 100 10
 * "第一次"排序基准数: 45
 * 从后往前找 找到比基准数小的数 和基准数位置进行交换;
 * 10 28 80 90 50 16 100 15
 * 从前往后找 找到比基准数大的数 和基准数位置进行交换
 * 10 28 45 90 50 16 100 80
 * <p>
 * 重复上面的操作进行排序 将所有的位置的数据都找完后 "第一次" 基准数排序完成
 * 10 28 16 90 50 45 100 80
 * 10 28 16 45 50 90 100 80
 * "第一次"基准数排序完后结果:
 * 以基准数分为3部分, 左边的基准数小, 右边的比基准数大
 * 然后对前部分 和 后部分 分别选择基准数进行排序
 * <p>
 * 什么时候截止?
 * <p>
 * 优化快速排序: 其实就是优化基准数
 * @Author houchenkai
 * @Created Date: 2021/7/12 11:46
 * @ClassName
 */
public class QuickSortDemo {


    public static void quickSort(int[] data, int left, int right) {

        // 选择基准数
        int base = data[left];
        int baseIndex = left;
        // 从前面往后找  找比基准数大的数
        // 从前面的哪个位置开始往后找
        int ll = left;
        // 从后面往前找  找比基准数小的数
        // 从后面的哪个位置开始往前找
        int rr = right;

        // 当 ll > rr 或者 ll=rr 的时候说明 按照此基准数的排序  已经排序完成
        while (ll < rr) {
            // 从后往前找 找比基准数小的数
            // 当跳出循环时 说明 已经找到比基准数小的数  此数位置rr
            while (ll < rr && data[rr] >= base) {
                rr--;
            }
            //  这里还用 ll < rr 说明是以 data[rr] >= base 不满足 跳出循环的
            if (ll < rr) {

                int temp = data[rr];
                // data[rr]是比基准数小的数  将data[rr]和基准数交换
                data[rr] = data[baseIndex];
                data[baseIndex] = temp;
                // 交换完后 rr位置 就是基准数的位置下标
                baseIndex = rr;
                // 此时 ll ++ ; 说明第一个数是已经排序的 从前往后找是 需从ll++开始
                ll++;
            }

            while (ll < rr && data[ll] <= base) {
                ll++;
            }

            if (ll < rr) {
                // data[rr]此时是基准数  将基准数的 data[ll]交换
                int temp = data[rr];
                data[rr] = data[ll];
                data[ll] = temp;
                rr--;
            }

        }
        // 开始第二次基准数排序
        // 递归 进行后续的快排
        if (left < ll) {
            quickSort(data, left, ll - 1);
        }
        if (rr < right) {
            quickSort(data, ll + 1, right);
        }

    }
}
